public class Sort3 {
    // 归并排序---递归
public static void mergeSort(int[] array){
    mergeSort(array,0,array.length-1);
    }
public static void mergeSort(int[] array,int left,int right){
    if(left>=right) return;
    int mid=(left+right)/2;
    //递归左边
    mergeSort(array, left, mid);
    //递归右边
    mergeSort(array,mid+1,right);
    //归并
    merge(array,left,right,mid);
    }
public static void merge(int[] array,int start,int end,int mid){
      int[] tmparr=new int[end-start+1];
      int i=0;
      int s1=start;
      int e1=mid;
      int s2=mid+1;
      int e2=end;
      //逐一比较，放入新数组
      while(s1<=e1 && s2<=e2){
          if(array[s1]<=array[s2]){
              tmparr[i++]=array[s1++];
          }else{
              tmparr[i++]=array[s2++];
          }
      }
      //将剩余部分一次性放入
    while(s1<=e1){
        tmparr[i++]=array[s1++];
    }
    while(s2<=e2){
        tmparr[i++]=array[s2++];
    }
    //将排序好的关键字放入原数组
    for(int k=0;k<i;k++){
        array[k+start]=tmparr[k];
    }
    }
// 归并排序---非递归
public static void mergeSort2(int[] array){
        //将数组分割成不同大小的部分，逐级归并
    int gap=1;
    while(gap<=array.length){
        for(int i=0;i<array.length;i+=2*gap){
            int s1=i;
            int e1=s1+gap-1;
            //防止越界 做出调整
            if(e1>array.length-1) e1=array.length-1;
            int s2=s1+gap;
            if(s2>array.length-1) s2=array.length-1;
            int e2=s2+gap-1;
            if(e2>array.length-1) e2=array.length-1;
            merge(array,s1,e2,e1);
        }
        gap*=2;
    }
    }

// 计数排序
public static void countSort(int[] array){
       int min=array[0];
       int max=array[0];
       //寻找范围区间，从而确定临时数组大小
       for(int i=0;i<array.length;i++){
           if(array[i]<min) {
               min=array[i];
           }else if(array[i]>max) {
               max=array[i];
           }
       }
       int length=max-min+1;
       int[] tmparr=new int[length];
       //根据出现的次数在范围数组里进行计数
       for(int i=0;i<array.length;i++){
           tmparr[array[i]-min]+=1;
       }
       int j=0;
       //根据出现次数将数组还原成排序后的数组
       for(int i=0;i<tmparr.length;i++){
           while(j<array.length && tmparr[i]>0){
               array[j++]=i+min;
               tmparr[i]-=1;
           }
       }
    }

}
